	virtual T* nextSetNode(int i);

	virtual long nextCompl(int i);

	virtual T* nextComplNode(int i);

	virtual T* treeNode(long i);

	virtual bool setNode(long i, T* newword);

	virtual bool isInTree(long i);

	ArrayvEBTree(int sz);

	virtual vEBTree<T> * clone();

	long nextSetElement(long i);

	virtual void toSet(long i);

	virtual void toCompl(long i);

	virtual void flipElement(long i);

	virtual bool isInSet(long i);

	virtual bool isInCompl(long i);

	virtual bool isInTree(int lvl, long i);

	virtual T* treeNode(int lvl, long i);

	virtual const T * toArray(long* size);

	virtual T * toArray(T * a);

	virtual long size();

	virtual void allToSet();

	virtual void allToCompl();

	virtual void logicneg();

	virtual void logicneg(vEBTree<T> * res);

	virtual void logicxor(vEBTree<T> * v);

	virtual void logicor(vEBTree<T> * v);

	virtual void logicor(vEBTree<T> * v, vEBTree<T> * res);

	virtual void logicxor(vEBTree<T> * v, vEBTree<T> * res);

	virtual void logicand(vEBTree<T> * v, vEBTree<T> * res);

	virtual void logicnegor(vEBTree<T> * v);

	virtual void logicnegand(vEBTree<T> * v);

	virtual void logicnegor(vEBTree<T> * v, vEBTree<T> * res);

	virtual void logicnegand(vEBTree<T> * v, vEBTree<T> * res);

	virtual void logicorneg(vEBTree<T> * v);

	virtual void logicandneg(vEBTree<T> * v);

	virtual void logicorneg(vEBTree<T> * v, vEBTree<T> * res);

	virtual void logicandneg(vEBTree<T> * v, vEBTree<T> * res);

	virtual void logicnor(vEBTree<T> * v);

	virtual void logicnand(vEBTree<T> * v);

	virtual void logicnor(vEBTree<T> * v, vEBTree<T> * res);

	virtual void logicnand(vEBTree<T> * v, vEBTree<T> * res);

	virtual long firstInSet();

	virtual long firstInCompl();

	virtual long cardOfSet();

	virtual long cardOfCompl();


	virtual void logicand(vEBTree<T> * v);

	virtual vEBTree<T>::Iterator * newSetIterator(FilterContainer<vEBTree<T> > * f);

	virtual bool isInTree(int lvl, long i);

	virtual T* treeNode(int lvl, long i);

	virtual void restart();

	virtual void restartFrom(long i);

	virtual long nextElement();

	FilteredIterator(vEBTree<T> * t, FilterContainer<vEBTree<T> > * f);


	emplate <typename T>
	inline vEBTree<T>::Iterator::Iterator(vEBTree<T> * t, FilterContainer<vEBTree<T> > * f) : logb(t->logb), maskb(t->maskb), height(t->height), n(t->n), f(f), t(t) {
	}

	template <typename T>
	inline vEBTree<T>::Iterator::Iterator(vEBTree<T> * t) : logb(t->logb), maskb(t->maskb), height(t->height), n(t->n), f(NULL), t(t) {
	}

	template <typename T>
	inline vEBTree<T>::Iterator::Iterator(vEBTree<T> * t, int l) : logb(t->logb), maskb(t->maskb), height(l+1), n(t->n), f(NULL), t(t) {
	}

	template <typename T>
	inline vEBTree<T>::Iterator::~Iterator() {
	}

	template <typename T>
	inline void vEBTree<T>::Iterator::restart() {
		idx = 0;
		node = t->treeNode(height-1, 0);
		nextidx = nextLeastElement(node, -1);
	}

	template <typename T>
	inline void vEBTree<T>::Iterator::restartFrom(long i) {
		idx = i;
		if (t->isInTree(height-1, levelidx(idx))) {
			node = t->treeNode(height-1, levelidx(idx));
			nextidx = nextLeastElement(node, wordidx(idx));
		}
		else {
			node = NULL;
			nextidx = -1;
		}
	}

	template <>
	inline int vEBTree<unsigned long long>::Iterator::nextLeastElement(unsigned long long * w, int i) {
		return __builtin_ffsll(*w & __maskll[i + 1])-1;
	}

	template <>
	inline int vEBTree<unsigned long>::Iterator::nextLeastElement(unsigned long * w, int i) {
		return __builtin_ffsl(*w & __maskl[i + 1])-1;
	}

	template <>
	inline int vEBTree<unsigned int>::Iterator::nextLeastElement(unsigned int * w, int i) {
		return __builtin_ffs(*w & __mask[i + 1])-1;
	}

	template <typename T>
	inline vEBTree<T>::FilteredIterator::FilteredIterator(vEBTree<T> * t, FilterContainer<vEBTree<T> > * f) : Iterator(t, f) {
	}

	template <typename T>
	inline vEBTree<T>::FilteredIterator::~FilteredIterator() {
	}

	template <typename T>
	inline void vEBTree<T>::FilteredIterator::restart() {
		this->idx = 0;
		ft = this->f->getvEBTree();
		this->node = this->t->treeNode(this->height-1, 0);
		fnode = ft->treeNode(this->height-1, 0L);
		word = *this->node & *fnode;
		this->nextidx = nextLeastElement(&word, -1);
	}

	template <typename T>
	inline void vEBTree<T>::FilteredIterator::restartFrom(long i) {
		this->idx = i;
		ft = this->f->getvEBTree();
		this->node = this->t->treeNode(this->height-1, levelidx(this->idx));
		fnode = ft->treeNode(this->height-1, levelidx(this->idx));
		word = *this->node & *fnode;
		this->nextidx = nextLeastElement(&word, wordidx(this->idx));
	}

	template <typename T>
	inline long vEBTree<T>::Iterator::nextElement() {
		if (nextidx < 0) {
			int l = height - 1;
			int wi;

			idx >>= logb;

			do {
				wi = wordidx(idx);
				idx = levelidx(idx);
				nextidx = nextLeastElement(t->treeNode(--l, idx), wi);
			} while (l > 0 && nextidx < 0);

			if (nextidx >= 0) {
				while (++l < height) {
					idx = (idx << logb) + nextidx;
					nextidx = nextLeastElement(t->treeNode(l, idx), -1);
				}

				node = t->treeNode(height-1, idx);
				idx = (idx << logb) + nextidx;
				nextidx = nextLeastElement(node, nextidx);
			}
			else
				idx = n;
		}
		else {
			idx = leveldspl(idx) + nextidx;
			nextidx = nextLeastElement(node, wordidx(idx));
		}

		return idx;
	}

	template <typename T>
	inline long vEBTree<T>::FilteredIterator::nextElement() {
		if (this->nextidx < 0) {
			int thish = this->height;
			int l = thish - 1;
			int wi;

			while (this->nextidx < 0 && this->idx < this->n) {
				this->idx >>= this->logb;
				do {
					wi = wordidx(this->idx);
					this->idx = levelidx(this->idx);
					if (ft->isInTree(--l, this->idx)) {
						word = *this->t->treeNode(l, this->idx) & *ft->treeNode(l, this->idx);
						this->nextidx = nextLeastElement(&word, wi);
					}
				} while (l > 0 && this->nextidx < 0);

				if (this->nextidx >= 0) {
					while (++l < thish && this->nextidx >= 0) {
						this->idx = (this->idx << this->logb) + this->nextidx;
						if (ft->isInTree(l, this->idx)) {
							word = *this->t->treeNode(l, this->idx) & *ft->treeNode(l, this->idx);
							this->nextidx = nextLeastElement(&word, -1);
						}
						else
							this->nextidx = -1;
					}

					if (this->nextidx >= 0) {
						this->node = this->t->treeNode(thish-1, this->idx);
						fnode = ft->treeNode(thish-1, this->idx);
						this->idx = (this->idx << this->logb) + this->nextidx;
						word = *this->node & *fnode;
						this->nextidx = nextLeastElement(&word, this->nextidx);
					}
				}
				else
					this->idx = this->n;
			}
		}
		else {
			this->idx = leveldspl(this->idx) + this->nextidx;
			this->nextidx = nextLeastElement(&word, wordidx(this->idx));
		}

		return this->idx;
	}

	template <typename T>
	inline long vEBTree<T>::Iterator::levelidx(long i) {
		return i >> logb;
	}

	template <typename T>
	inline int vEBTree<T>::Iterator::wordidx(long i) {
		return i & maskb;
	}

	template <typename T>
	inline long vEBTree<T>::Iterator::leveldspl(long i) {
		return i & ~maskb;
	}

	template <typename T>
	inline vEBTree<T>::vEBTree(long n) : bitvector(NULL), n(n) {
		int i, l;
		logn = inline_ceillog(n, 1);
		logw = inline_ceillog(sizeof(T), 1);
		logb = logw + 3;
		maskb = ~(-1L << logb);
		word_size = 1LL << logb;
	//	printf("n = %ld  logw = %d  logb = %d\n", n, logw, logb);

		height = logn / logb;
		if (logn != height * logb || height == 0)
			height++;
	}

	template <typename T>
	inline vEBTree<T>::~vEBTree() {
		if (bitvector != NULL)
			delete bitvector;
	}

	template <typename T>
	inline long vEBTree<T>::nextSetElement(long i) {
		setIt->restartFrom(i);
		return setIt->nextElement();
	}

	template <typename T>
	inline void vEBTree<T>::toSet(long i) {
		long ii = i;
		int h = height - 1;
		long p = i >> logb;
		while (h > 0 && *treeNode(h, p) == 0) {
			*treeNode(h--, p) |= (1LL << (ii & maskb));
			ii = p;
			p >>= logb;
		}
		*treeNode(h, p) |= (1LL << (ii & maskb));
	}

	template <typename T>
	inline void vEBTree<T>::flipElement(long i) {
		long ii = i;
		int h = height - 1;
		long p = i >> logb;
		T mask = (1LL << (ii & maskb));
		while (h > 0 && (*treeNode(h, p) == 0 || *treeNode(h, p) == mask)) {
			*treeNode(h--, p) ^= mask;
			ii = p;
			p >>= logb;
			mask = (1LL << (ii & maskb));
		}
		*treeNode(h, p) ^= (1LL << (ii & maskb));
	}

	template <typename T>
	inline bool vEBTree<T>::isInSet(long i) {
		int dspl = (logb*(height-1));
		long ii = i >> dspl;
		long p = ii >> logb;
		int h = 0;
		while (h < height - 1 && ((1LL << (ii & maskb)) & *treeNode(h, p)) != 0) {
			h++;
			p = ii;
			dspl -= logb;
			ii = i >> dspl;
		}
		return (h == height - 1 && ((1LL << (ii & maskb)) & *treeNode(h, p)) != 0);
	}

	template <typename T>
	inline void vEBTree<T>::toCompl(long i) {
		long ii = i;
		int h = height - 1;
		long p = i >> logb;
		while (h > 0 && *treeNode(h, p) == 0) {
			ii = p;
			p >>= logb;
			*treeNode(--h, p) &= ~(1LL << (ii & maskb));
		}
	}

	template <typename T>
	inline const T * vEBTree<T>::toArray() {
		long f = n >> logb;
		if (n != (f << logb))
			f++;
		if (bitvector == NULL)
			bitvector = new T[f];

		int i;
		for (i = 0; i < f; i++)
			bitvector[i] = *treeNode(height-1, i);
		return bitvector;
	}

	template <typename T>
	inline T * vEBTree<T>::toArray(T * a) {
		long f = n >> logb;
		if (n != (f << logb))
			f++;

		int i;
		for (i = 0; i < f; i++)
			a[i] = *treeNode(height-1, i);

		return a;
	}

	template <typename T>
	inline long vEBTree<T>::wordIdx(long i) {
		return i >> logb;
	}

	template <typename T>
	inline int vEBTree<T>::inWordIdx(long i) {
		return i & maskb;
	}
